package com.frank.code_notes.C01_array;

/**
 * @Description 704.二分查找
 * @Author zhoujr
 * @Data 2024/11/21 14:53
 */
public class L704BinarySearch {

    /**
     * [left, right]
     */
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) >> 1); // 非负数 + 负偶数， >> 1相当于/2， 负奇数不行
            if (nums[middle] == target) {
                return middle;
            }
            if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    /**
     * [left, right)
     */
    public static int searchTwo(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        System.out.println(searchTwo(new int[]{-1, 0, 3, 5, 9, 12}, 9));
        System.out.println(searchTwo(new int[]{-1, 0, 3, 5, 9, 12}, 2));
        System.out.println(search(new int[]{-1,0,3,5,9,12}, 9));
        System.out.println(search(new int[]{-1,0,3,5,9,12}, 2));
    }
}
